﻿// poj3579 Median.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

/*

http://poj.org/problem?id=3579

中位数
时间限制：1000MS 内存限制：65536K
总提交量。23007 被接受。7641
说明

给定N个数字X1, X2, ... ，XN，让我们计算每一对数字的差。∣Xi-Xj∣（1≤i＜j≤N）。
通过这个工作，我们可以得到C(N,2)个差值，现在你的任务是尽快找到差值的中位数!

注意在这个问题中，中位数的定义是：如果m，即差异的数量是偶数，那么中位数就是第（m/2）个最小的数字。
例如，在m=6的情况下，你必须找到第三个最小的数字。

输入

输入由几个测试案例组成。
在每个测试案例中，第一行将给出N。然后给出N个数字，代表X1, X2, .... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

输出

对于每个测试案例，在一个单独的行中输出中位数。

样本输入
4
1 3 2 4
3
1 10 2
样本输出
1
8
*/



/*
题意：给定N个数，两两做差取绝对值，再找出这些绝对值的中位数。
也就是给n个数放在数组a中，求出C(n,2)个|a[i] - a[j]|数中的的中位数。
思路：对数组a排序后，估计一个两两做差的绝对值的集合的中位数mid，
与a[i]的差大于mid（也就是某个数大于a[i] + mid）的那些数的个数如果小于C(n,2) / 2的话，
说明mid太大了。以此为条件进行第一重二分搜索，第二重二分搜索是对X的搜索，直接用lower_bound实现。
*/

#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <cstdio>
using namespace std;

// 计算组合数
long long C(int m, int n)
{
	int p = 1;
	int q = 1;
	for (int i = 1; i <= n; i++)
	{
		p *= (m - i + 1);
		q *= i;
	}
	return p / q;
}

// 判断mid作为中位数是否太大。执行此操作前数组a必须排序。
bool Check(int* a, int n, int mid)
{
	int sum = 0;
	// 与a[i]的差大于mid（也就是某个数大于a[i] + mid）的那些数的个数之和
	// 遍历每一个a[i]，求大于或者等于mid+a[i]的个数
	for (int i = 0; i < n; i++)
	{
		// lower_bound(a + i + 1, a + n, mid + a[i])表示在a[i+1]到a[n-1]中二分查找大于或者等于mid+a[i]的第一个元素的位置
		sum += (a + n) - lower_bound(a + i + 1, a + n, mid + a[i]);
	}
	// 如果满足sum <= C(n, 2) / 2，说明大于或等于中位数的元素没有超过半数或者正好等于半数，分为这么4种可能：
	//1、大于或等于中位数mid（我们估计的）的这部分元素包含了这个中位数mid（我们估计的），
	//个数正好等于半数，说明元素个数有偶数个，而后半截的第一个元素是这个中位数mid（我们估计的），
	//显然应该是mid的前一个元素才是真正的中位数，说明mid估大了；
	//2、大于或等于中位数mid（我们估计的）的这部分元素不包含这个中位数mid（我们估计的），
	//个数正好等于半数，说明元素个数有偶数个，而后半截的第一个元素大于mid，前半截最后一个元素小于mid，
	//显然应该是mid的前一个元素才是真正的中位数，说明mid估大了；
	//3、大于或等于中位数mid（我们估计的）的这部分元素包含了这个中位数mid（我们估计的），
	//个数小于半数，说明后半截的第一个元素是这个中位数mid（我们估计的），又因为后半截的元素个数不足半数，
	//显然说明mid估大了；
	//4、大于或等于中位数mid（我们估计的）的这部分元素不包含了这个中位数mid（我们估计的），
	//个数小于半数，说明后半截的第一个元素大于mid（我们估计的），前半截的最后一个元素小于mid，
	//又因为后半截的元素个数不足半数，显然说明mid估大了；
	// 综合1、2、3、4，如果满足sum <= C(n, 2) / 2这种情况反正就是估大了
	return sum <= C(n, 2) / 2; // 返回true就是估大了，返回false就是估小了或者正好
}

int main()
{
	int n = 0;
	//while (cin >> n)
	while (scanf("%d", &n) == 1)
	{
		int* a = new int[n];
		for (int i = 0; i < n; i++)
		{
			//cin >> a[i];
			scanf("%d", &a[i]);
		}
		sort(a, a + n);
		long long lb = 0; // 两两做差取绝对值可能的最小值
		long long ub = a[n - 1] - a[0]; // 两两做差取绝对值可能的最大值
		// 为什么循环条件是ub - lb > 1？是因为ub、lb、mid都是整数，由于mid会向下取整，
		//所以当ub-lb=1时，mid为lb，而此时真正的中位数要么为ub，要么为lb，
		//也就是中位数mid要么估的正好，要么估低了，在循环体内，只会走else分支，下届lb被修正为mid，是同样的值，并没有改变，
		//于是陷入死循环，因此循环条件不能写成ub - lb >= 1或者ub - lb >=0，只能写成ub - lb > 1。
		// 当循环条件为ub - lb > 1时，在循环快结束时，必定有ub-lb=2，最终mid的值lb+1，而此时真正的中位数要么为ub，要么为lb，要么为lb+1。
		// 如果真正的中位数为ub，说明mid估低了，在循环体内，走else分支，修正lb的值，在原先的值的基础上加1，得到了真实的中位数的值，随后循环结束；
		// 如果真正的中位数为lb，说明mid估高了，在循环体内，走if分支，修正ub的值，然后循环结束；
		// 如果真正的中位数为lb+1，说明mid估的正好，在循环体内，走else分支，修正lb的值，在原先的值的基础上加1，得到了真实的中位数的值，随后循环结束；
		// 综上，循环条件必须写成ub - lb > 1，循环结束后，lb就是确切的中位数的值
		while (ub - lb > 1)
		{
			int mid = (lb + ub) >> 1; // 尝试新的中位数，
			bool flag = Check(a, n, mid);
			// 如果中位数猜测的太大
			if (flag)
			{
				ub = mid; // 修改上界。
			}
			// 如果中位数猜测的太小，或者小于中位数的元素个数正好等于半数
			else
			{
				lb = mid; // 修改下界。
			}
		}
		//cout << lb << "\n";
		printf("%lld\n", lb);
		delete[] a;
	}
	return 0;
}